「数理計画」なんて聞くと、いかにも難しそうで
とっつきにくい印象を受けてしまいますが、実際は私たちにとっても
身近なもので、役に立つものです。誰でも（不十分とはいえ）
毎日なんとなく数理計画をしているものなのです！
数理計画を簡単にいうと、「計算によって一番良いやり方を見つける」
ということです。
ごくごく簡単な例を考えてみましょう。
お菓子を買いに行きました。
Aセットは100円で15個入り
Bセットは150円で25個入り
Cセットは200円で30個入り
のとき、どれを買うのが一番得でしょう？
こんなのは当然、1個当たりいくらなのかを計算してみればいいですね。
Aセット ・・・ 100÷15 = 6.6円/個
Bセット ・・・ 150÷25 = 6.0円/個
Cセット ・・・ 200÷30 = 6.6円/個
という結果から1個当たりの値段が一番安いBセットを買うことが最適で
あると分かりました。
こういうのって日常的に自然とやってますよね？
このように、いろいろな可能性から一番良いものを見つけることを
最適化(optimization)
といい、これが数理計画の目的になります。
実際には数理計画の理論はもっと複雑な問題にも適用でき、
あちこちで使われています。
例えば
・生産計画
・在庫計画
・流通計画
・スケジュール計画
・経済計画 ・・・・ etc.
などなど、挙げればきりがありません。
実務的な問題では10万を超える変数から最適なものを見つけることも可能です。
とにかく、数理計画はスゴいのです。
もともとは数学の難しい理論なので、使いこなすにはそれなりの知識が必要ですが
GLPKを用いればモデリング(modeling)という作業により、勝手に
解いてもらえます。
GLPKで遊んで、数理計画の深遠な世界を是非堪能してみてください！
では実際に簡単な例を通してモデリングという作業と、GLPKの使い方を確認していきましょう。
ミックスジュース屋さんの一日を考えます。
このお店では、「イチゴバナナ」「リンゴバナナ」「デラックス」という
3種類のミックスジュースを売っています。
「イチゴバナナ」は1リットル当たり900円
「リンゴバナナ」は1リットル当たり800円
「デラックス」 は1リットル当たり1100円だとします。
さて、材料はどうなっているかというと、
「イチゴバナナ」は、イチゴとバナナを3:7でミックスします。
「リンゴバナナ」は、リンゴとバナナを5:5でミックスします。
「デラックス」は、イチゴ、バナナ、リンゴを3:3:4でミックスします
また、1日に使える材料は上限があって、
バナナは50リットル
イチゴは30リットル
リンゴは50リットルまでしか使えません。
さて、あなたが店長なら、このお店の売り上げを最大にするには
それぞれの商品を何リットルずつ作ったら良いでしょうか？
頭の中で勘に頼ったり、経験に基づいたやり方をしてみても、
それが本当に最適なのか分かりませんし(保証がない)、確かめるのも困難ですよね。
こういうときには、与えられた問題を数式に直して考えます。
これを定式化といいます。
考えやすいように、「イチゴバナナ」の生産量をx1
「リンゴバナナ」をx2、「デラックス」をx3とおきます。
まず、売上を考えます。
それぞれの値段×生産量ですから
900×x1 + 800×x2 + 1100×x3 ですね？
これを最大化するのが目的です。
このような条件を目的関数(objective function)といいます。
次にイチゴの使用量を考えます。
1リットル当たりで考えると、
「イチゴバナナ」では0.3リットル、「デラックス」でも0.3リットル使用されます。
また、上限が30リットルと決まっているので
0.3×x1 + 0.3×x3 ≦ 30 と書けますね？
この式は生産量x1〜x3を決めるルールとなります。
このような条件を制約条件(constraint)といいます。
つまり、この制約条件をやぶらない範囲でx1〜x3が決められるのです。
同様にリンゴの使用量を考えますと、
「リンゴバナナ」で0.5リットル、「デラックス」で0.4リットル使われ
上限が50リットルですから
0.5×x2 + 0.4×x3 ≦ 50
で、バナナの使用量は
「イチゴバナナ」で0.7リットル、「リンゴバナナ」で0.5リットル、
「デラックス」で0.3リットル使われます。
上限が50リットルですから
0.7×x1 + 0.5*×2 + 0.3×x3 ≦ 50
これで全ての目的関数と制約条件がそろいましたから
まとめておきます。
変数x1(イチゴバナナ) 変数x2(リンゴバナナ) 変数x3(デラックス) 最大化: 900*x1 + 800*x2 + 1100*x3 イチゴの上限:0.3*x1 + 0.3*x3 <= 30; リンゴの上限: 0.5*x2 + 0.4*x3 <= 50; バナナの上限:0.7*x1 + 0.5*x2 + 0.3*x3 <= 50;
GLPKでは、これを下のように書きます。
var x1 >= 0; var x2 >= 0; var x3 >= 0; maximize profit: 900*x1 + 800*x2 + 1100*x3; s.t. strawberry: 0.3*x1 + 0.3*x3 <= 30; s.t. apple: 0.5*x2 + 0.4*x3 <= 50; s.t. banana: 0.7*x1 + 0.5*x2 + 0.3*x3 <= 50;
まったく同じように対応しているのが分かりますか？
varとは、変数を表すキーワードです。
生産量はマイナスにならないので、「>=0」と書いて正であると決めています。
最大化の条件はmaximizeと書きます。
＃最小化ではminimizeを使います。
後ろの「profit」は式に名前を付けているだけで別の名前でも構いません。
ただし、他の制約式や変数と同じ名前してはダメです。
s.t.とは「subject to」の略で「〜に従う」という意味です。
よって制約条件になります。
目的関数と同じように式に「banana」など名前を付けています。
では、このモデルを解いてみましょう。
手計算でもできますが、せっかくですからGLPKを使います。
このモデルをファイルに保存して「.mod」という拡張子をつけてください。
通例として普通モデルには「.mod」を使います。
これをモデルファイルといいます。
できたら、GLPKをインストールしたフォルダにおき、
MS-DOSプロンプトを起動し、そのフォルダに移ってください。
ここではC:\glpk-4.4\にインストールしたと仮定し、話を進めます。
また、ファイル名は「mix.mod」とつけたとします。
できたら以下のようにタイプしてください。
C:\glpk-4.4\>glpsol -m mix.mod -o mix.txt
なにやら表示されましたか？
そうしたら、そのフォルダを見ると「mix.txt」というファイルができているのが
分かると思います。ここに解いた結果が書き込まれるのです。
いろいろありますが、「Objective: profit = 131500 (MAXimum)」というところを
見てください。これが最適値(objective value)です。
つまり、最大で131500の売上が見込めることになります。
また、
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 x1 B 12.5 0
2 x2 B 30 0
3 x3 B 87.5 0
というところを見てください。
これが最適解(optimal solution)での生産量です。
要するに、「イチゴバナナ」を12.5リットル、「リンゴバナナ」を30リットル、
「デラックス」を87.5リットル生産するのが一番よいということが分かります。
嘘だと思ったらこれ以上良い組合せを見つけてみてください。
GLPKを使えばこのような問題は一瞬で解いてくれるのです。
最後になりましたが、このように1次不等式(等式でも可)だけで
目的関数や制約条件が記述される最適化問題を線形計画法(LP)といいます。
LPは「Linear Programming」の略で、GLPKの「LとP」の名前の由来にもなっています。
LPは単体法(simplex method)とか
内点法(interior method)というアルゴリズムが使われていて
非常に高速に解くことができます。
今のコンピュータなら変数が10万(！！）を超えても大丈夫です。
さて、GLPKではLPに関しては非常に簡単に解くことができることが
なんとなく分かって頂けたでしょうか。
でもちょっと待ってください。
じつは上で示したモデリングはあまり良い例ではないのです。
例えば、一日の材料の上限が変わったり、値段が変わったりしたら
どうしましょう？いちいちモデルを直して回るのでしょうか？
もしかしたらそこでミスするかも知れませんし、めんどくさいです。
また、今は変数の数が3つでしたが、これが10万だったらどうでしょう？
x1+x2+x3+・・・x99999+x100000などと書くのでしょうか？
このように、実はもっとまとまった良い書き方があるのです。
いきなりですが、まずはそれを示してみます。
# mix2.mod
set Prod;
set Material;
param value{Prod};
param limit{Material};
param require{Prod,Material};
var X{Prod} >= 0;
maximize PROFIT:sum{p in Prod}X[p]*value[p];
s.t. LIMIT{m in Material}: sum{p in Prod}X[p]*require[p,m] <= limit[m];
# mix2.dat set Prod := strawbanana applebanana deluxe; set Material := strawberry apple banana; param value := strawbanana 900 applebanana 800 deluxe 1100; param limit := strawberry 30 apple 50 banana 50; param require: strawberry apple banana := strawbanana 0.3 0.0 0.7 applebanana 0.0 0.5 0.5 deluxe 0.3 0.4 0.3;
やれやれ、急に難しく見えますね（ｗ
分かるところから見ていきましょう。
まず、ファイルを2つに分離しています。
先ほどはモデルファイルだけでしたが、今度は
拡張子「.dat」のデータファイルが
作られています。
2つに分けた理由はデータだけを後で自由にいじれるように
するためです。
つまり、モデルは変更せずに済むので変なミスが混入しにくくなり、
また、モデルファイルを独立した道具として扱えるのです！
次に、modファイル内の新登場のキーワードについて説明します。
set 集合名; (集合の定義)
param パラメータ名{依存する集合名}; (パラメータの定義)
パラメータ(parameter)とは、この問題でいうところの
「値段」や「原料の使用量」など、モデル中で具体的な数字
となるもののことです。
具体的な数字はモデル中に直接記述せずに、パラメータという形にすることによって
後から数値が変わったときにも簡単に変更することができます。
また後で見るように、1つの式にまとめやすくなります。
集合(set)とは、パラメータがどの値に影響されるか？というものを
集めたものです。
これは少々分かりにくいのですが、ここでいうと「商品」や「原料」が集合にあたります。
なぜなら、パラメータ「値段」は「イチゴバナナ」「リンゴバナナ」「デラックス」に
よって変わります。このとき、「イチゴバナナ」「リンゴバナナ」「デラックス」を
「商品」という集合でまとめてやることによって、
「値段」は「商品」によって決まると表すことができます。
「値段」をvalue、「商品」をProdと表すことにすると、
これをGLPKでは
set Prod;
param value{Prod};
と書くことができます。
このように、集合は先にパラメータありきで「何に依存するか？」と考えると考えやすいと思います。
モデルファイルは目的関数や制約式の形を表現し、
データファイルは実際の数値を表現します。
たとえば、
{ 2x + 3y ≦ 9
{ 5x + 4y ≧3
という制約式と、
{ 4x - 2y ≦ 10
{ -3x + 5y ≧0
という制約式は数値は違いますが
{ ax + by ≦ c
{ dx + ey ≧ f
という形は共通ですよね。
イメージ的には
{ ax + by ≦ c
{ dx + ey ≧ f
という式を記述するのがモデルファイルで
a=2, b=3, c=9
d=5, e=4, f=3
という数値を記述するのがデータファイルです。
こうすれば問題が変わっても
データファイルだけもう一つ作ればよい
のでむだがありません。
普通のプログラムで外からデータを与えるのと同じです。
そうでないと、常に同じ動作のソフトになってしまい、
おもしろくも何ともないですからね。
ただ眺めているだけのゲームソフトを想像してみてください（ｗ
# mix2.mod
set Prod;
set Material;
param value{Prod};
param limit{Material};
param require{Prod,Material};
var X{Prod} >= 0;
maximize PROFIT:sum{p in Prod}X[p]*value[p];
s.t. LIMIT{m in Material}: sum{p in Prod}X[p]*require[p,m] <= limit[m];
まず、paramについて説明します。
これはパラメータのことで、上記した
a=2, b=3, c=9・・・のような具体的な数値データです。
5行目の param value{Prod}; という式をみてみましょう。
valueというのがパラメータ名です。(ここでは価格という意味)
うしろの{Prod}とは、Prodよって決まるということを
表します。
具体的にいえばProdとはいまProductionの略で、製品を表しています。
つまり、param value{Prod}; は、製品ごとの価格
という意味になります。
ここで定義したパラメータ名と意味は以下の通りです。
require(必要量)は、製品と原材料の2つの集合から決まるパラメータなので
{Prod, Material}を与えています。
value{Prod} ・・・ 製品ごとの価格
limit{Material} ・・・ 原材料の上限
require{Prod,Material} ・・・ 製品ごとの原材料必要量
つぎにsetについて説明します。
これは集合のことで、paramのところで説明した
「〜によって決まる」のうち、「〜」の部分に当たります。
集合を定義しなければパラメータも定義できませんから、
普通は集合、パラメータの順に定義します。
先に set Prod; としてProd(製品)という集合を定義しておき
それを使って param value{Prod}; のようにパラメータを定義します。
集合はパラメータだけでなく、変数や制約式の定義にも利用しますから
きちんと設計してなにが必要か、問題によってうまく決めなければなりません。
大きな問題ではこの集合の取り方にセンスが現れるといっても
過言ではありません。
最後にvarについて説明します。
最初のモデルでは、x1,x2,x3としていましたが、
今回は集合を導入したので、製品の生産量という意味から
var X{Prod};
と書けます。
ここまでくれば集合を用いた定義について分かったのではないでしょうか。
次に目的関数・制約式の説明に入ります。
数理計画ではいきなりモデリングを行うのではなく、
数式による定式化を行います。
すると、この問題の場合、以下のように定式化できます。
基本的には、これに従ってモデル化するだけです。
まず、すべての式には名前が必要なので、適当な名前としてPROFITと
しておきます。
目的関数は利益最大化なので、(製品の価格)×(製品の生産量)が
一つの製品に対する利益となり、
それをすべて足し合わせたものが全体の利益になります。
よって、製品の価格を意味するVに、生産量を意味するXをかけ、
Σを前に置いて総和をとればよいということが分かります。
GLPKのモデルではΣはsum、
∈ に当たる部分はinに相当します。 (a∈A は aが集合Aの元であることを表します)
添字だった部分はC言語のように[ ]に入れてください。
よって、目的関数は
maximize PROFIT:sum{p in Prod}X[p]*value[p];
となります。定式化ができれば、このように後は記号を置き換えるだけです。
簡単ですね。
制約式も同様に、
s.t. LIMIT{m in Material}: sum{p in Prod}X[p]*require[p,m] <= limit[m];
とすればOKです。
上との違いは式の前にも添字がついていることでしょうか。
これは、原材料の上限が、すべての原材料(Material)によって決まる
ことを示しています。
つまり、「リンゴ」「バナナ」「イチゴ」のそれぞれの原材料に上限があるからです。
GLPK内部ではこの式を3つの制約式に展開して扱っています。
# mix2.dat set Prod := strawbanana applebanana deluxe; set Material := strawberry apple banana; param value := strawbanana 900 applebanana 800 deluxe 1100; param limit := strawberry 30 apple 50 banana 50; param require: strawberry apple banana := strawbanana 0.3 0.0 0.7 applebanana 0.0 0.5 0.5 deluxe 0.3 0.4 0.3;
データファイルでは、今まで定義したすべてのパラメータに
具体的な数字を代入していきます。
GLPKでは代入するということを表す記号として:=を使います。
まず、集合の定義からみていきましょう。
モデルでは「製品」「原材料」という分類しかしていませんでしたが、
データでは具体的な製品名を入れていきます。
例えば、「イチゴバナナ」をstrawbananaと表していますね。
それをスペース区切りで入れます。
カンマ区切りじゃないので注意！！
次にパラメータのセッティングです。
valueとlimitはそれぞれ一つの集合によって決まりますから、
1次元のデータになります。
最初に集合の要素名、後に値という書式で入れていきます。
例えば、「イチゴバナナの値段」ならば
strawbanana 900
という感じです。
すべての集合要素について定義したら最後は
セミコロンを忘れないでください。
require(必要量)は2つの集合(製品,原材料)によって決まるパラメータです。
例えば、デラックス(製品)を作るときにリンゴ(原材料)はいくつ必要か？
のようになるからです。
これは2次元のデータとして記述します。
まず、パラメータ名の後ろをコロン(:)で区切ります。
そして、横に並べた要素名が「列」
縦に並べた要素名が「行」となります。
あとは、座標のように縦と横の交点に値を書いていけばOKです。
なお、a[m,n]の様にした場合は、
mが行で、nが列です。
「行列」と覚えておくとわかりやすいです！
いろいろ書いてきましたが、こんなものを全部覚える必要はありません。 ( ← えっ！？)
今回使ったようなサンプルを少しずつ改造して、徐々に分かっていけばいいのです。
ただ何の説明もないと辛いですから、最低限の説明をしたまでです。
数理計画は一日にしてならず。同じ問題に対してもいろいろな定式化やモデリングの仕方があって、
それぞれ効率も全く違います。
少しずつでいいので、楽しみながら勉強していくのが
もっともよい方法だと思います。
次回は整数計画について書いていきたいと思います。
それでは！